package com.heima.leetcode.practice;

/**
 * <strong>各位相加，数字根 leetcode 258</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/12 21:31
 */
public class E258 {

    /**
     * <h3>方法一：原始方式</h3>
     * @param num 数字
     * @return 各位相加结果
     */
    public int addDigits1(int num) {
        if (num < 10) {
            return num;
        }
        int result = 0;
        while (num >= 10) {
            result += num % 10;
            num /= 10;
        }
        result += num;
        return addDigits1(result);
    }

    /**
     * <h3>方法二：优化为模9运算，迭代法</h3>
     * @param num 数字
     * @return 各位相加结果
     */
    public int addDigits2(int num) {
        while (num >= 10){
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }

    // 数字根：数字根是一个非负整数的各位数字之和，直到结果为一位数为止

    // 0
    // 1  2  3  4  5  6  7  8  9
    // 10 11 12 13 14 15 16 17 18
    // 19 20 21 22 23 24 25 26 27
    // 28 29 30 31 32 33 34 35 36
    // 37 38 39 40 41 42 43 44 45
    // 对于任何一个数N有：

    // 1、N == 0     =>  数字根 = 0
    // 2、N % 9 == 0 =>  数字根 = 9
    // 3、N % 9 != 0 =>  数字根 = N % 9

    // 证明：
    // 假设有 N = 1000 * a + 100 * b + 10 * c + d
    // => N mod 9 = (999 * a + a + 99 * b + b + 9 * c + c + d) mod 9
    // => N mod 9 = (a + b + c + d) mod 9
    // N各位之和记为N1：N1 = a + b + c + d
    // 那么 N1 也可以化成 1000 * a + 100 * b + 10 * c + d 类似的形式
    // N1各位之和记为N2
    // 同理可得 N1 mod 9 = N2 mod 9
    // 也就是说N 和 N1同余，N1 和 N2同余，N2和N3同余……直到NL(最后一个，肯定是一位数)
    // 可得N和NL同余
    // 而这里的NL不是别的，就是N的数字根
    // N mod 9 == 数字根 mod 9
    // 当 N的数字根 == 9时：N mod 9 == 0
    // 当 1 <= N的数字根 <= 8时，N mod 9 == 数字根
    // 当 N的数字根 == 0时，N 只能是 0，因为只有当N的权重都为0时数字根才会是0

    /**
     * <h3>方法二：优化为模9运算，还是递归</h3>
     * @param num 数字
     * @return 各位相加结果
     */
    public int addDigits3(int num) {
        if (num == 0){
            return 0;
        }
        if (num % 9 == 0){
            return 9;
        }
        return num % 9;
    }
}
